





<!DOCTYPE html>
<html class="writer-html5" lang="zh-CN" >
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>InferBound Pass &mdash; tvm 0.8.dev1982 文档</title>
  

  
  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css" integrity="sha384-Gn5384xqQ1aoWXA+058RXPxPg6fy4IWvTNh0E263XmFcJlSAwiGgFAW/dAiS6JXm" crossorigin="anonymous">
  <link rel="stylesheet" href="../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
  <link rel="stylesheet" href="../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../_static/gallery.css" type="text/css" />
  <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
  <link rel="stylesheet" href="../_static/css/tlcpack_theme.css" type="text/css" />

  
  
    <link rel="shortcut icon" href="../_static/tvm-logo-square.png"/>
  

  
  
  
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
        <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
        <script src="../_static/jquery.js"></script>
        <script src="../_static/underscore.js"></script>
        <script src="../_static/doctools.js"></script>
        <script src="../_static/translations.js"></script>
    
    <script type="text/javascript" src="../_static/js/theme.js"></script>

    
    <script type="text/javascript" src="../_static/js/tlcpack_theme.js"></script>
    <link rel="index" title="索引" href="../genindex.html" />
    <link rel="search" title="搜索" href="../search.html" />
    <link rel="next" title="混合前端开发指南" href="hybrid_script.html" />
    <link rel="prev" title="Pass Infrastructure" href="pass_infra.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    
<header class="header">
    <div class="innercontainer">
      <div class="headerInner d-flex justify-content-between align-items-center">
          <div class="headerLogo">
               <a href="https://tvm.apache.org/"><img src=https://tvm.apache.org/assets/images/logo.svg alt="logo"></a>
          </div>

          <div id="headMenu" class="headerNav">
            <button type="button" id="closeHeadMenu" class="navCloseBtn"><img src="../_static/img/close-icon.svg" alt="Close"></button>
             <ul class="nav">
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/community>Community</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/download>Download</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/vta>VTA</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/blog>Blog</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvm.apache.org/docs>Docs</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvmconf.org>Conference</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://github.com/apache/tvm/>Github</a>
                </li>
                <li class="nav-item">
                   <a class="nav-link" href=https://tvmchinese.github.io/declaration_zh_CN.html>About-Translators</a>
                </li>
             </ul>
               <div class="responsivetlcdropdown">
                 <button type="button" class="btn-link">
                   ASF
                 </button>
                 <ul>
                     <li>
                       <a href=https://apache.org/>Apache Homepage</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/licenses/>License</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/foundation/sponsorship.html>Sponsorship</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/security/>Security</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/foundation/thanks.html>Thanks</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/events/current-event>Events</a>
                     </li>
                     <li>
                       <a href=https://www.zhihu.com/column/c_1429578595417563136>Zhihu</a>
                     </li>
                 </ul>
               </div>
          </div>
            <div class="responsiveMenuIcon">
              <button type="button" id="menuBtn" class="btn-menu"><img src="../_static/img/menu-icon.svg" alt="Menu Icon"></button>
            </div>

            <div class="tlcDropdown">
              <div class="dropdown">
                <button type="button" class="btn-link dropdown-toggle" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
                  ASF
                </button>
                <div class="dropdown-menu dropdown-menu-right">
                  <ul>
                     <li>
                       <a href=https://apache.org/>Apache Homepage</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/licenses/>License</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/foundation/sponsorship.html>Sponsorship</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/security/>Security</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/foundation/thanks.html>Thanks</a>
                     </li>
                     <li>
                       <a href=https://www.apache.org/events/current-event>Events</a>
                     </li>
                     <li>
                       <a href=https://www.zhihu.com/column/c_1429578595417563136>Zhihu</a>
                     </li>
                  </ul>
                </div>
              </div>
          </div>
       </div>
    </div>
 </header>
 
    <nav data-toggle="wy-nav-shift" class="wy-nav-side fixed">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="../index.html">
          

          
            
            <img src="../_static/tvm-logo-small.png" class="logo" alt="Logo"/>
          
          </a>

          
            
            
                <div class="version">
                  0.8.dev1982
                </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        
        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <p class="caption" role="heading"><span class="caption-text">如何开始</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../install/index.html">安装 TVM</a></li>
<li class="toctree-l1"><a class="reference internal" href="../contribute/index.html">贡献者指南</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">用户引导</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../tutorial/index.html">User Tutorial</a></li>
<li class="toctree-l1"><a class="reference internal" href="../how_to/index.html">How To Guides</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">开发者引导</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../dev/tutorial/index.html">Developer Tutorial</a></li>
<li class="toctree-l1"><a class="reference internal" href="../dev/how_to/how_to.html">开发者指南</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">架构指南</span></p>
<ul class="current">
<li class="toctree-l1 current"><a class="reference internal" href="index.html">Design and Architecture</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="index.html#example-compilation-flow">编译流程示例</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#logical-architecture-components">逻辑架构组件</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-support">tvm/support</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-runtime">tvm/runtime</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-node">tvm/node</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-ir">tvm/ir</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-target">tvm/target</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-tir">tvm/tir</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-arith">tvm/arith</a></li>
<li class="toctree-l2 current"><a class="reference internal" href="index.html#tvm-te">tvm/te</a><ul class="current">
<li class="toctree-l3 current"><a class="current reference internal" href="#">InferBound Pass</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#itervar-hyper-graph">IterVar 超图</a></li>
<li class="toctree-l4"><a class="reference internal" href="#passdowndomain">PassDownDomain</a></li>
<li class="toctree-l4"><a class="reference internal" href="#inferrootbound">InferRootBound</a></li>
<li class="toctree-l4"><a class="reference internal" href="#inferbound-with-compute-at">InferBound with compute_at</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="hybrid_script.html">混合前端开发指南</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-topi">tvm/topi</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-relay">tvm/relay</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#tvm-autotvm">tvm/autotvm</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#frontends">Frontends</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#security">安全</a></li>
<li class="toctree-l2"><a class="reference internal" href="index.html#microtvm">microTVM</a></li>
</ul>
</li>
</ul>
<p class="caption" role="heading"><span class="caption-text">主题引导</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../topic/microtvm/index.html">microTVM：裸机使用TVM</a></li>
<li class="toctree-l1"><a class="reference internal" href="../topic/vta/index.html">VTA: Versatile Tensor Accelerator</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">参考指南</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../reference/langref/index.html">语言参考</a></li>
<li class="toctree-l1"><a class="reference internal" href="../reference/api/python/index.html">Python API</a></li>
<li class="toctree-l1"><a class="reference internal" href="../reference/api/links.html">Other APIs</a></li>
<li class="toctree-l1"><a class="reference internal" href="../reference/publications.html">Publications</a></li>
<li class="toctree-l1"><a class="reference internal" href="../genindex.html">索引</a></li>
</ul>

            
          
        </div>
        
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
      
      <nav class="wy-nav-top" aria-label="top navigation" data-toggle="wy-nav-top">
        
            <div class="togglemenu">

            </div>
            <div class="nav-content">
              <!-- tvm -->
              Table of content
            </div>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        

          




















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="../index.html">Docs</a> <span class="br-arrow">></span></li>
        
          <li><a href="index.html">Design and Architecture</a> <span class="br-arrow">></span></li>
        
      <li>InferBound Pass</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
            <a href="../_sources/arch/inferbound.rst.txt" rel="nofollow"> <img src="../_static//img/source.svg" alt="viewsource"/></a>
          
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="inferbound-pass">
<span id="dev-inferbound-pass"></span><h1>InferBound Pass<a class="headerlink" href="#inferbound-pass" title="永久链接至标题">¶</a></h1>
<p>InferBound在normalize之后、ScheduleOps之前发生 <a class="reference external" href="https://github.com/apache/tvm/blob/main/python/tvm/driver/build_module.py">build_module.py</a>。 它的主要作用是创建边界（bound）的映射表，记录程序中每一个循环变量（IterVar）的范围。这些边界在ScheduleOps中，用于设置For循环节点的extent域， 参考 <a class="reference external" href="https://github.com/apache/tvm/blob/main/src/te/operation/op_util.cc">MakeLoopNest</a>, 以及用于设置缓存（buffer）的大小 (<a class="reference external" href="https://github.com/apache/tvm/blob/main/src/te/operation/compute_op.cc">BuildRealize</a>), 等等。</p>
<p>InferBound的输出是一个从循环变量（IterVar）到其范围（Range）的映射表：</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="n">Map</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="p">,</span> <span class="n">Range</span><span class="o">&gt;</span> <span class="n">InferBound</span><span class="p">(</span><span class="k">const</span> <span class="n">Schedule</span><span class="o">&amp;</span> <span class="n">sch</span><span class="p">);</span>
</pre></div>
</div>
<p>因此，让我们回顾一下 Range 和 IterVar 类：</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="k">namespace</span> <span class="n">HalideIR</span> <span class="p">{</span>
<span class="k">namespace</span> <span class="n">IR</span> <span class="p">{</span>
     <span class="k">class</span> <span class="nc">RangeNode</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Node</span> <span class="p">{</span>
     <span class="k">public</span><span class="o">:</span>
             <span class="n">Expr</span> <span class="n">min</span><span class="p">;</span>
             <span class="n">Expr</span> <span class="n">extent</span><span class="p">;</span>
             <span class="c1">// remainder ommitted</span>
     <span class="p">};</span>
     <span class="p">}}</span>

<span class="k">namespace</span> <span class="n">tvm</span> <span class="p">{</span>
     <span class="k">class</span> <span class="nc">IterVarNode</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Node</span> <span class="p">{</span>
     <span class="k">public</span><span class="o">:</span>
             <span class="n">Range</span> <span class="n">dom</span><span class="p">;</span>
             <span class="n">Var</span> <span class="n">var</span><span class="p">;</span>
             <span class="c1">// remainder ommitted</span>
     <span class="p">};</span>
<span class="p">}</span>
</pre></div>
</div>
<p>请注意，IterVarNode 还包含一个Range <code class="docutils literal notranslate"><span class="pre">dom</span></code> 成员变量。此 <code class="docutils literal notranslate"><span class="pre">dom</span></code>  可能有或可能没有有意义的值，具体取决于 IterVar 的创建时间。例如，当调用 <code class="docutils literal notranslate"><span class="pre">tvm.compute</span></code> 时，会为每个空间轴和规约轴`创建一个IterVar&lt;<a class="reference external" href="https://github.com/apache/tvm/blob/main/src/te/operation/compute_op.cc">https://github.com/apache/tvm/blob/main/src/te/operation/compute_op.cc</a>&gt;` ，这时dom也就等于调用 <code class="docutils literal notranslate"><span class="pre">tvm.compute</span></code> 时所提供的形状（shape）。</p>
<p>另一方面，当 <code class="docutils literal notranslate"><span class="pre">tvm.split</span></code> 被调用时，会`为内部轴和外部轴创建 IterVar&lt;<a class="reference external" href="https://github.com/apache/tvm/blob/main/src/te/schedule/schedule_lang.cc">https://github.com/apache/tvm/blob/main/src/te/schedule/schedule_lang.cc</a>&gt;` ，但并没有给这些 IterVar 赋予有意义的 <code class="docutils literal notranslate"><span class="pre">dom</span></code> 值。</p>
<p>在任何情况下，IterVar 的 <code class="docutils literal notranslate"><span class="pre">dom</span></code> 成员变量在 InferBound 期间都不会被修改。但是，请记住，IterVar 的 <code class="docutils literal notranslate"><span class="pre">dom</span></code> 成员变量有时用作范围（Ranges）计算的默认值。</p>
<p>为了理解 InferBound pass，接下来我们将回顾一些 TVM 代码库的概念。</p>
<p>回想一下， InferBound 需要一个 Schedule 引用类型的参数。这个 schedule 对象及其成员包含了有关正在编译的程序的所有信息。</p>
<p>TVM schedule 由阶段（Stage）组成。每个阶段只有一个操作（Operation），例如 ComputeOp 或 TensorComputeOp 。而每个操作都有一个 root_iter_vars 列表，在 ComputeOp 的情况下，该列表由轴循环变量（axis IterVars）和规约轴循环变量（reduce IterVars）组成。每个操作还可以包含许多其他循环变量（IterVar），但这些循环变量都会由操作的 IterVarRelations 列表相关联。每个 IterVarRelation 表示 schedule 中的拆分（split）、融合（fuse）或变基（rebase）。例如，在拆分的情况下，IterVarRelation 指定了被拆分的父循环变量（parent IterVar）和两个子循环变量（children IterVar）：内部循环变量和外部循环变量。</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="k">namespace</span> <span class="n">tvm</span> <span class="p">{</span>
     <span class="k">class</span> <span class="nc">ScheduleNode</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Node</span> <span class="p">{</span>
     <span class="k">public</span><span class="o">:</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">Operation</span><span class="o">&gt;</span> <span class="n">outputs</span><span class="p">;</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">Stage</span><span class="o">&gt;</span> <span class="n">stages</span><span class="p">;</span>
             <span class="n">Map</span><span class="o">&lt;</span><span class="n">Operation</span><span class="p">,</span> <span class="n">Stage</span><span class="o">&gt;</span> <span class="n">stage_map</span><span class="p">;</span>
             <span class="c1">// remainder omitted</span>
     <span class="p">};</span>

     <span class="k">class</span> <span class="nc">StageNode</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Node</span> <span class="p">{</span>
     <span class="k">public</span><span class="o">:</span>
             <span class="n">Operation</span> <span class="n">op</span><span class="p">;</span>
             <span class="n">Operation</span> <span class="n">origin_op</span><span class="p">;</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="o">&gt;</span> <span class="n">all_iter_vars</span><span class="p">;</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="o">&gt;</span> <span class="n">leaf_iter_vars</span><span class="p">;</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">IterVarRelation</span><span class="o">&gt;</span> <span class="n">relations</span><span class="p">;</span>
             <span class="c1">// remainder omitted</span>
     <span class="p">};</span>

     <span class="k">class</span> <span class="nc">OperationNode</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Node</span> <span class="p">{</span>
     <span class="k">public</span><span class="o">:</span>
             <span class="k">virtual</span> <span class="n">Array</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="o">&gt;</span> <span class="n">root_iter_vars</span><span class="p">();</span>
             <span class="k">virtual</span> <span class="n">Array</span><span class="o">&lt;</span><span class="n">Tensor</span><span class="o">&gt;</span> <span class="n">InputTensors</span><span class="p">();</span>
             <span class="c1">// remainder omitted</span>
     <span class="p">};</span>

     <span class="k">class</span> <span class="nc">ComputeOpNode</span> <span class="o">:</span> <span class="k">public</span> <span class="n">OperationNode</span> <span class="p">{</span>
     <span class="k">public</span><span class="o">:</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="o">&gt;</span> <span class="n">axis</span><span class="p">;</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="o">&gt;</span> <span class="n">reduce_axis</span><span class="p">;</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">Expr</span><span class="o">&gt;</span> <span class="n">body</span><span class="p">;</span>
             <span class="n">Array</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="o">&gt;</span> <span class="n">root_iter_vars</span><span class="p">();</span>
             <span class="c1">// remainder omitted</span>
     <span class="p">};</span>
<span class="p">}</span>
</pre></div>
</div>
<p>至此还未提及张量（Tensor），但在 TVM 中，张量表示一个操作（Operation）输出。</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">TensorNode</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Node</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
     <span class="c1">// The source operation, can be None</span>
     <span class="c1">// This Tensor is output by this op</span>
     <span class="n">Operation</span> <span class="n">op</span><span class="p">;</span>
     <span class="c1">// The output index from the source operation</span>
     <span class="kt">int</span> <span class="n">value_index</span><span class="p">;</span>
<span class="p">};</span>
</pre></div>
</div>
<p>在上面的 Operation 类声明中，我们可以看到每个操作都有一个 InputTensor 列表。因此，schedule 的所有阶段形成了一张有向无环图（DAG），其中每个阶段就是图中的节点。如果阶段 B 的操作有一个输入张量，其源操作是阶段 A 中的操作，则从阶段 A 到阶段 B 存在一条边。 简单地说，如果 B 消耗 A 产生的张量，则从 A 到 B 有一条边。请参阅下面的图。在InferBound的开头通过调用 <cite>CreateReadGraph &lt;https://github.com/apache/tvm/blob/main/src/te/schedule/bound.cc&gt;</cite> 创建了这张图。</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/stage_graph.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/stage_graph.png" />
<p>InferBound 遍历一次图，每个阶段正好访问一次。InferBound 从输出阶段开始（即上图中的蓝色实心节点），然后向上移动（延着边的相反方向）。这是通过对图的节点执行反向拓扑排序来实现的。因此，当 InferBound 访问一个阶段时，其每个消费者阶段就已经被访问了。</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/inferbound_traversal.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/inferbound_traversal.png" />
<p>InferBound pass 的伪代码如下所示：</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="n">Map</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="p">,</span> <span class="n">Range</span><span class="o">&gt;</span> <span class="n">InferBound</span><span class="p">(</span><span class="k">const</span> <span class="n">Schedule</span><span class="o">&amp;</span> <span class="n">sch</span><span class="p">)</span> <span class="p">{</span>
     <span class="n">Array</span><span class="o">&lt;</span><span class="n">Operation</span><span class="o">&gt;</span> <span class="n">outputs</span> <span class="o">=</span> <span class="n">sch</span><span class="o">-&gt;</span><span class="n">get_outputs</span><span class="p">();</span>
     <span class="n">G</span> <span class="o">=</span> <span class="n">CreateGraph</span><span class="p">(</span><span class="n">outputs</span><span class="p">);</span>
     <span class="n">stage_list</span> <span class="o">=</span> <span class="n">sch</span><span class="o">-&gt;</span><span class="n">reverse_topological_sort</span><span class="p">(</span><span class="n">G</span><span class="p">);</span>
     <span class="n">Map</span><span class="o">&lt;</span><span class="n">IterVar</span><span class="p">,</span> <span class="n">Range</span><span class="o">&gt;</span> <span class="n">rmap</span><span class="p">;</span>
     <span class="k">for</span> <span class="p">(</span><span class="n">Stage</span> <span class="n">s</span> <span class="n">in</span> <span class="n">stage_list</span><span class="p">)</span> <span class="p">{</span>
             <span class="n">InferRootBound</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">rmap</span><span class="p">);</span>
             <span class="n">PassDownDomain</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">rmap</span><span class="p">);</span>
     <span class="p">}</span>
     <span class="k">return</span> <span class="n">rmap</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
</div>
<p>InferBound pass 有两个有趣的属性，不是明显：</p>
<ol class="arabic simple">
<li><p>在 InferBound 访问一个 stage 后，该 stage 中所有 IterVars 的范围将被设置在 <code class="docutils literal notranslate"><span class="pre">rmap</span></code> 中。</p></li>
<li><p>每个 IterVar 的范围只在 <code class="docutils literal notranslate"><span class="pre">rmap</span></code> 中设置一次，然后永远不会改变。</p></li>
</ol>
<p>因此，有必要解释下 InferBound 在访问一个阶段时的作用。如上文的伪代码所示，InferBound 在每个阶段调用两个函数：InferRootBound 和 PassDownDomain。InferRootBound 的目的是设置该阶段的每个 root_iter_var 的 Range（在 <code class="docutils literal notranslate"><span class="pre">rmap</span></code> 中）。（注：InferRootBound 不会设置其他任何 IterVar 的 Range，而只会设置属于 root_iter_vars 的 IterVar Range）。PassDownDomain 的目的是将该信息传播到阶段的其余 IterVar。当 PassDownDomain 返回时， 阶段中的所有 IterVar 在 <code class="docutils literal notranslate"><span class="pre">rmap</span></code> 都有对应的 Range。</p>
<p>该文档的其余部分深入探讨了 InferRootBound 和 PassDownDomain 的细节。由于 PassDownDomain 更易于描述，我们将先介绍它。</p>
<div class="section" id="itervar-hyper-graph">
<span id="itervarhypergraph"></span><h2>IterVar 超图<a class="headerlink" href="#itervar-hyper-graph" title="永久链接至标题">¶</a></h2>
<p>如上所述，InferBound pass 遍历了由阶段组成的图。但是，在每个阶段中都有另外一张图，其节点都是 IterVar。InferRootBound 和 PassDownDomain 在这些 IterVar 图上执行消息的传递。</p>
<p>回想一下，该阶段的所有 IterVar 都与 IterVarRelation 相关。阶段的 IterVarRelation 形成了有向无环超图，其中图的每个节点对应一个 IterVar，超图的每条边对应于一个 IterVarRelation。我们还可以将此超图表示为 DAG，这样更易于可视化，如下图所示。</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/relations.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/relations.png" />
<p>上图显示了一个阶段的 IterVar 超图。该阶段有一个 root_iter_var，<code class="docutils literal notranslate"><span class="pre">i</span></code>。它已经被拆分，并且由此产生的内轴 <code class="docutils literal notranslate"><span class="pre">i.inner</span></code> 再次被拆分。该阶段的 leaf_iter_var 用绿色表示：<code class="docutils literal notranslate"><span class="pre">i.outer</span></code>，<code class="docutils literal notranslate"><span class="pre">i.inner.outer</span></code> 和 <code class="docutils literal notranslate"><span class="pre">i.inner.inner</span></code>。</p>
<p>消息传递函数的名称为 “PassUp” 或 “PassDown”，具体取决于消息是从子节点传递到 DAG 中的父节点（”PassUp”），还是从父节点传递给其子节点（”PassDown”）。例如，上图左侧的大箭头表明 PassDownDomain 会从根 IterVar <code class="docutils literal notranslate"><span class="pre">i</span></code> 向其子节点 <code class="docutils literal notranslate"><span class="pre">i.outer</span></code> 和 <code class="docutils literal notranslate"><span class="pre">i.inner</span></code> 发送消息。</p>
</div>
<div class="section" id="passdowndomain">
<span id="id1"></span><h2>PassDownDomain<a class="headerlink" href="#passdowndomain" title="永久链接至标题">¶</a></h2>
<p>PassDownDomain 的目的是获取 InferRootBound 为 root_iter_var 产生的 Range ，并为阶段中所有其他  IterVar 设置 Range。</p>
<p>PassDownDomain 会遍历阶段的 IterVarRelation。IterVarRelation 有三种可能的类型：拆分、融合和变基。而最有趣的类型（因为它提供了改进的机会）是表示拆分的 IterVarRelation。</p>
<p>拆分的内部 IterVar 和外部 IterVar 的 Range 是根据父 IterVar 的已知 Range 来设置的，如下所示：</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="n">rmap</span><span class="p">[</span><span class="n">split</span><span class="o">-&gt;</span><span class="n">inner</span><span class="p">]</span> <span class="o">=</span> <span class="n">Range</span><span class="o">::</span><span class="n">FromMinExtent</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">split</span><span class="o">-&gt;</span><span class="n">factor</span><span class="p">)</span>
<span class="n">rmap</span><span class="p">[</span><span class="n">split</span><span class="o">-&gt;</span><span class="n">outer</span><span class="p">]</span> <span class="o">=</span> <span class="n">Range</span><span class="o">::</span><span class="n">FromMinExtent</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">DivCeil</span><span class="p">(</span><span class="n">rmap</span><span class="p">[</span><span class="n">split</span><span class="o">-&gt;</span><span class="n">parent</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">extent</span><span class="p">,</span> <span class="n">split</span><span class="o">-&gt;</span><span class="n">factor</span><span class="p">))</span>
</pre></div>
</div>
<p>当 <code class="docutils literal notranslate"><span class="pre">split-&gt;factor</span></code> 没有均匀地划分父级的范围（extent）时，就有机会收紧 InferBound 产生的边界。假设父级的范围是 20，拆分系数是 16。然后在外循环的第二次迭代中，内循环只需要执行 4 次迭代，而不是 16 次迭代。如果 PassDownDomain 能够将 <code class="docutils literal notranslate"><span class="pre">split-&gt;inner</span></code> 的范围设置为 <code class="docutils literal notranslate"><span class="pre">min(split-&gt;factor,</span> <span class="pre">rmap[split-&gt;parent]-&gt;extent</span> <span class="pre">-</span> <span class="pre">(split-&gt;outer</span> <span class="pre">*</span> <span class="pre">split-&gt;factor))</span></code> ，那么内部变量的范围将根据正在执行的外循环的迭代进行适当的调整。</p>
<p>对于融合类型的关系，融合IterVar 的 Range 是根据内部 IterVar  和外部 IterVar 的已知 Range 来设置的，如下所示：</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="n">rmap</span><span class="p">[</span><span class="n">fuse</span><span class="o">-&gt;</span><span class="n">fused</span><span class="p">]</span> <span class="o">=</span> <span class="n">Range</span><span class="o">::</span><span class="n">FromMinExtent</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">rmap</span><span class="p">[</span><span class="n">fuse</span><span class="o">-&gt;</span><span class="n">outer</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">extent</span> <span class="o">*</span> <span class="n">rmap</span><span class="p">[</span><span class="n">fuse</span><span class="o">-&gt;</span><span class="n">inner</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">extent</span><span class="p">)</span>
</pre></div>
</div>
</div>
<div class="section" id="inferrootbound">
<h2>InferRootBound<a class="headerlink" href="#inferrootbound" title="永久链接至标题">¶</a></h2>
<p>回想一下， InferBound 调用了 InferRootBound，然后在阶段图中的每个阶段调用 <a class="reference internal" href="#passdowndomain"><span class="std std-ref">PassDownDomain</span></a> 。InferRootBound 的目的是设置阶段的操作(operation)的每个 root_iter_var 范围。这些范围将使用 <a class="reference internal" href="#passdowndomain"><span class="std std-ref">PassDownDomain</span></a>  被传播到阶段的其余 IterVars。请注意，InferRootBound 不会设置任何其他 IterVar 的范围，而只会设置那些属于该阶段的 root_iter_vars。</p>
<p>如果该阶段是输出阶段或者占位符，InferRootBound 只需将 root_iter_var 范围设置为其默认值。root_iter_var 的默认范围取自 Itvar 的 <code class="docutils literal notranslate"><span class="pre">dom</span></code> 成员（请参阅上面的 IterVarNode 类声明）。</p>
<p>否则，InferRootBound 会遍历该阶段的消费者，并为每个消费者的 IterVars 创建 IntSet ，具体如下。阶段 1） 为消费者的 leaf_iter_vars 初始化 IntSet ，并通过 PassUpDomain 传播到消费者的root_iter_vars（阶段2）。这些 IntSet 用于创建消费者阶段的输入张量的  TensorDom（阶段3）。最后，在处理完所有消费者之后，InferRootBound 将会调用 GatherBound ，根据 TensorDoms 设置阶段的 root_iter_vars 的范围（阶段 4）。</p>
<p>This process can seem complicated. One reason is that a stage can have more than one consumer. Each consumer has different requirements, and these must somehow be consolidated. Similarly, the stage may output more than one tensor, and each consumer only uses a particular subset of these tensors. Furthermore, even if a consumer uses a particular tensor, it may not use all elements of the tensor.</p>
<p>As mentioned above, a consumer may only require a small number of elements from each tensor. The consumers can be thought of as making requests to the stage, for certain regions of its output tensors. The job of Phases 1-3 is to establish the regions of each output tensor that are required by each consumer.</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/inferbound_phases.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/inferbound_phases.png" />
<div class="section" id="intsets">
<h3>IntSets<a class="headerlink" href="#intsets" title="永久链接至标题">¶</a></h3>
<p>During InferRootBound, Ranges are converted to IntSets, and message passing is performed over IntSets. Therefore, it is important to understand the difference between Ranges and IntSets. The name “IntSet” suggests it can represent an arbitrary set of integers, e.g., A = {-10, 0, 10, 12, 13}. This would certainly be more expressive than a Range, which only represents a set of contiguous integers, e.g., B = {10,11,12}.</p>
<p>However, currently IntSets come in only three varieties: IntervalSets, StrideSets, and ModularSets. IntervalSets, similarly to Ranges, only represent sets of contiguous integers. A StrideSet is defined by a base IntervalSet, a list of strides, and a list of extents. However, StrideSet is unused, and ModularSet is only used by the frontend.</p>
<p>Therefore, not all sets of integers can be represented by an IntSet in TVM currently. For example, set A in the example above can not be represented by an IntSet. However, in future the functionality of IntSet can be extended to handle more general kinds of integer sets, without requiring modification to users of IntSet.</p>
<p><em>InferBound is more complicated for schedules that contain compute_at. Therefore, we first explain InferBound for schedules that do not contain compute_at.</em></p>
</div>
<div class="section" id="phase-1-initialize-intsets-for-consumer-s-leaf-iter-vars">
<span id="phase1"></span><h3>Phase 1: Initialize IntSets for consumer’s leaf_iter_vars<a class="headerlink" href="#phase-1-initialize-intsets-for-consumer-s-leaf-iter-vars" title="永久链接至标题">¶</a></h3>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="cm">/*</span>
<span class="cm"> * Input: Map&lt;IterVar, Range&gt; rmap: contains the Range for each IterVar of the consumer stage</span>
<span class="cm"> * Output: Map&lt;IterVar, IntSet&gt; up_state: contains an IntSet for each leaf_iter_var of the consumer</span>
<span class="cm"> */</span>
</pre></div>
</div>
<p>In Phase 1, IntSets for each of the consumer’s leaf_iter_vars are created, based on the Ranges of the leaf_iter_vars from <code class="docutils literal notranslate"><span class="pre">rmap</span></code>.  Recall that the consumer has already been visited by InferBound, so all of its IterVars have known Ranges in <code class="docutils literal notranslate"><span class="pre">rmap</span></code>.</p>
<p>有以下三种情况：</p>
<ul class="simple">
<li><p>Case 1: Extent of leaf var’s Range is 1. In this case, the up_state for the leaf is just a single point, equal to the Range’s min.</p></li>
<li><p>Case 2: <em>No relaxation is needed. In this case, the up_state for the leaf is just a single point, defined by the leaf var itself.</em></p></li>
<li><p>Case 3: Relaxation is needed. In this case, the leaf’s Range is simply converted to an IntSet.</p></li>
</ul>
<p>For simplicity, we assume the schedule does not contain thread axes. In this case, Case 2 is only relevant if the schedule contains compute_at. Please refer to the section <a class="reference internal" href="#inferboundca"><span class="std std-ref">InferBound with compute_at</span></a>, for further explanation.</p>
</div>
<div class="section" id="phase-2-propagate-intsets-from-consumer-s-leaves-to-consumer-s-roots">
<span id="phase2"></span><h3>Phase 2: Propagate IntSets from consumer’s leaves to consumer’s roots<a class="headerlink" href="#phase-2-propagate-intsets-from-consumer-s-leaves-to-consumer-s-roots" title="永久链接至标题">¶</a></h3>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="cm">/*</span>
<span class="cm"> * Input: Map&lt;IterVar, IntSet&gt; up_state: consumer leaf -&gt; IntSet</span>
<span class="cm"> * Output: Map&lt;IterVar, IntSet&gt; dom_map: consumer root -&gt; IntSet</span>
<span class="cm"> */</span>
</pre></div>
</div>
<p>The purpose of Phase 2 is to propagate the IntSet information from the consumer’s leaf_iter_vars to the consumer’s root_iter_vars. The result of Phase 2 is another map, <code class="docutils literal notranslate"><span class="pre">dom_map</span></code>, that contains an IntSet for each of the consumer’s root_iter_vars.</p>
<p>Phase 2 begins by calling PassUpDomain, which visits the IterVarRelations of the consumer stage. In the case of a Split relation, PassUpDomain sets the up_state of the parent IterVar, based on the inner and outer IntSets, as follows:</p>
<ul class="simple">
<li><p>Case 1: The Ranges of outer and inner IterVars match their <code class="docutils literal notranslate"><span class="pre">up_state</span></code> domains. In this case, set the parent’s <code class="docutils literal notranslate"><span class="pre">up_state</span></code> by simply converting the parent’s Range to an IntSet.</p></li>
<li><p>Case 2: <em>Otherwise, the parent’s</em> <code class="docutils literal notranslate"><span class="pre">up_state</span></code> <em>is defined by evaluating</em> <code class="docutils literal notranslate"><span class="pre">outer*f</span> <span class="pre">+</span> <span class="pre">inner</span> <span class="pre">+</span> <span class="pre">rmap[parent]-&gt;min</span></code>, <em>with respect to the</em> <code class="docutils literal notranslate"><span class="pre">up_state</span></code> <em>of outer and inner. Here, instead of using the Split relation’s factor, TVM uses</em> <code class="docutils literal notranslate"><span class="pre">f</span> <span class="pre">=</span> <span class="pre">rmap[inner]-&gt;extent</span></code>.</p></li>
</ul>
<p>Case 2 is only needed if the schedule contains compute_at. Please refer to the section <a class="reference internal" href="#inferboundca"><span class="std std-ref">InferBound with compute_at</span></a> below, for further explanation.</p>
<p>After PassUpDomain has finished propagating up_state to all IterVars of the consumer, a fresh map, from root_iter_vars to IntSet, is created. If the schedule does not contain compute_at, the IntSet for root_iter_var <code class="docutils literal notranslate"><span class="pre">iv</span></code> is created by the following code:</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="n">dom_map</span><span class="p">[</span><span class="n">iv</span><span class="o">-&gt;</span><span class="n">var</span><span class="p">.</span><span class="n">get</span><span class="p">()]</span> <span class="o">=</span> <span class="n">IntSet</span><span class="o">::</span><span class="n">range</span><span class="p">(</span><span class="n">up_state</span><span class="p">.</span><span class="n">at</span><span class="p">(</span><span class="n">iv</span><span class="p">).</span><span class="n">cover_range</span><span class="p">(</span><span class="n">iv</span><span class="o">-&gt;</span><span class="n">dom</span><span class="p">));</span>
</pre></div>
</div>
<p>Note that if the schedule does not contain compute_at, Phases 1-2 are actually unnecessary. dom_map can be built directly from the known Ranges in rmap. Ranges simply need to be converted to IntSets, which involves no loss of information.</p>
</div>
<div class="section" id="phase-3-propagate-intsets-to-consumer-s-input-tensors">
<span id="phase3"></span><h3>Phase 3: Propagate IntSets to consumer’s input tensors<a class="headerlink" href="#phase-3-propagate-intsets-to-consumer-s-input-tensors" title="永久链接至标题">¶</a></h3>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="cm">/*</span>
<span class="cm"> * Input: Map&lt;IterVar, IntSet&gt; dom_map: consumer root -&gt; IntSet</span>
<span class="cm"> * Output: Map&lt;Tensor, TensorDom&gt; tmap: output tensor -&gt; vector&lt;vector&lt;IntSet&gt; &gt;</span>
<span class="cm"> */</span>
</pre></div>
</div>
<p>Note that the consumer’s input tensors are output tensors of the stage InferBound is working on. So by establishing information about the consumer’s input tensors, we actually obtain information about the stage’s output tensors too: the consumers require certain regions of these tensors to be computed. This information can then be propagated through the rest of the stage, eventually obtaining Ranges for the stage’s root_iter_vars by the end of Phase 4.</p>
<p>The output of Phase 3 is tmap, which is a map containing all of the stage’s output tensors. Recall that a Tensor is multi-dimensional, with a number of different axes. For each output tensor, and each of that tensor’s axes, tmap contains a list of IntSets. Each IntSet in the list is a request from a different consumer.</p>
<p>Phase 3 is accomplished by calling PropBoundToInputs on the consumer. PropBoundToInputs adds IntSets to tmap’s lists, for all input Tensors of the consumer.</p>
<p>The exact behavior of PropBoundToInputs depends on the type of the consumer’s operation: ComputeOp, TensorComputeOp, PlaceholderOp, ExternOp, etc. Consider the case of TensorComputeOp. A TensorComputeOp already has a Region for each of its Tensor inputs, defining the slice of the tensor that the operation depends on. For each input tensor i, and dimension j, a request is added to tmap, based on the corresponding dimension in the Region:</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="p">(</span><span class="kt">size_t</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">t</span><span class="p">.</span><span class="n">ndim</span><span class="p">();</span> <span class="o">++</span><span class="n">j</span><span class="p">)</span> <span class="p">{</span>
     <span class="c1">// i selects the Tensor t</span>
     <span class="n">tmap</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">EvalSet</span><span class="p">(</span><span class="n">region</span><span class="p">[</span><span class="n">j</span><span class="p">],</span> <span class="n">dom_map</span><span class="p">));</span>
<span class="p">}</span>
</pre></div>
</div>
</div>
<div class="section" id="phase-4-consolidate-across-all-consumers">
<span id="phase4"></span><h3>Phase 4: Consolidate across all consumers<a class="headerlink" href="#phase-4-consolidate-across-all-consumers" title="永久链接至标题">¶</a></h3>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="cm">/*</span>
<span class="cm"> * Input: Map&lt;Tensor, TensorDom&gt; tmap: output tensor -&gt; vector&lt;vector&lt;IntSet&gt; &gt;</span>
<span class="cm"> * Output: Map&lt;IterVar, Range&gt; rmap: rmap is populated for all of the stage&#39;s root_iter_vars</span>
<span class="cm"> */</span>
</pre></div>
</div>
<p>Phase 4 is performed by GatherBound, whose behavior depends on the type of operation of the stage. We discuss the ComputeOp case only, but TensorComputeOp is the same.</p>
<p>A ComputeOp has only a single output Tensor, whose axes correspond to the axis variables of the ComputeOp. The root_iter_vars of a ComputeOp include these axis variables, as well as the reduce_axis variables. If the root IterVar is an axis var, it corresponds to one of the axes of the output Tensor. GatherBound sets the Range of such a root IterVar to the union of all IntSets (i.e., union of all consumer requests) for the corresponding axis of the tensor. If the root IterVar is a reduce_axis, its Range is just set to its default (i.e., the <code class="docutils literal notranslate"><span class="pre">dom</span></code> member of IterVarNode).</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="c1">// &#39;output&#39; selects the output tensor</span>
<span class="c1">// i is the dimension</span>
<span class="n">rmap</span><span class="p">[</span><span class="n">axis</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">=</span> <span class="n">arith</span><span class="o">::</span><span class="n">Union</span><span class="p">(</span><span class="n">tmap</span><span class="p">[</span><span class="n">output</span><span class="p">][</span><span class="n">i</span><span class="p">]).</span><span class="n">cover_range</span><span class="p">(</span><span class="n">axis</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">dom</span><span class="p">);</span>
</pre></div>
</div>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/gatherbound.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/gatherbound.png" />
<p>The union of IntSets is computed by converting each IntSet to an Interval, and then taking the minimum of all minimums, and the maximum of all of these interval’s maximums.</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/union.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/union.png" />
<p>This clearly results in some unnecessary computation, i.e., tensor elements will be computed that are never used.</p>
<p>Unfortunately, even if we’re lucky and the IntervalSet unions do not produce unnecessary computation, the fact that GatherBound considers each dimension of the tensor separately can also cause unnecessary computation. For example, in the diagram below the two consumers A and B require disjoint regions of the 2D tensor: consumer A requires T[0:2, 0:2], and consumer B requires T[2:4, 2:4]. GatherBound operates on each dimension of the tensor separately. For the first dimension of the tensor, GatherBound takes the union of intervals 0:2 and 2:4, producing 0:4 (note that no approximation was required here). Similarly for the second dimension of the tensor. Therefore, the dimension-wise union of these two requests is T[0:4, 0:4]. So GatherBound will cause all 16 elements of tensor T to be computed, even though only half of those elements will ever be used.</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/gatherbound_problem.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/gatherbound_problem.png" />
</div>
</div>
<div class="section" id="inferbound-with-compute-at">
<span id="inferboundca"></span><h2>InferBound with compute_at<a class="headerlink" href="#inferbound-with-compute-at" title="永久链接至标题">¶</a></h2>
<p>If the schedule contains compute_at, Phases 1-2 of InferRootBound become more complex.</p>
<div class="section" id="motivation">
<h3>Motivation<a class="headerlink" href="#motivation" title="永久链接至标题">¶</a></h3>
<p><strong>Ex. 1</strong></p>
<p>Consider the following snippet of a TVM program:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">C</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span> <span class="p">:</span> <span class="n">tvm</span><span class="o">.</span><span class="n">const</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="s2">&quot;int32&quot;</span><span class="p">),</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;C&#39;</span><span class="p">)</span>
<span class="n">D</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span> <span class="p">:</span> <span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;D&#39;</span><span class="p">)</span>
</pre></div>
</div>
<p>This produces the following (simplified IR):</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">i</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span>
    <span class="k">for</span> <span class="n">j</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span>
        <span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="mi">5</span>
<span class="k">for</span> <span class="n">i</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span>
    <span class="k">for</span> <span class="n">j</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span>
        <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span>
</pre></div>
</div>
<p>It’s easy to see that stage D requires all (5,16) elements of C to be computed.</p>
<p><strong>Ex. 2</strong></p>
<p>However, suppose C is computed at axis j of D:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">s</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">create_schedule</span><span class="p">(</span><span class="n">D</span><span class="o">.</span><span class="n">op</span><span class="p">)</span>
<span class="n">s</span><span class="p">[</span><span class="n">C</span><span class="p">]</span><span class="o">.</span><span class="n">compute_at</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">D</span><span class="p">],</span> <span class="n">D</span><span class="o">.</span><span class="n">op</span><span class="o">.</span><span class="n">axis</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
</pre></div>
</div>
<p>Then only a single element of C is needed at a time:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">i</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span>
    <span class="k">for</span> <span class="n">j</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span>
        <span class="n">C</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">5</span>
        <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">C</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span>
</pre></div>
</div>
<p><strong>Ex. 3</strong></p>
<p>Similarly, if C is computed at axis i of D, only a vector of 16 elements of C are needed at a time:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">i</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span>
    <span class="k">for</span> <span class="n">j</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span>
        <span class="n">C</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="mi">5</span>
    <span class="k">for</span> <span class="n">j</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span>
        <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">C</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span>
</pre></div>
</div>
<p>Based on the above examples, it is clear that InferBound should give different answers for stage C depending on where in its consumer D it is “attached”.</p>
</div>
<div class="section" id="attach-paths">
<span id="attachpaths"></span><h3>Attach Paths<a class="headerlink" href="#attach-paths" title="永久链接至标题">¶</a></h3>
<p>If stage C is computed at axis j of stage D, we say that C is  <em>attached</em>  to axis j of stage D. This is reflected in the Stage object by setting the following three member variables:</p>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">StageNode</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Node</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="c1">// ommitted</span>

    <span class="c1">// For compute_at, attach_type = kScope</span>
    <span class="n">AttachType</span> <span class="n">attach_type</span><span class="p">;</span>

    <span class="c1">// For compute_at, this is the axis</span>
    <span class="c1">// passed to compute_at, e.g., D.op.axis[1]</span>
    <span class="n">IterVar</span> <span class="n">attach_ivar</span><span class="p">;</span>

    <span class="c1">// The stage passed to compute_at, e.g., D</span>
    <span class="n">Stage</span> <span class="n">attach_stage</span><span class="p">;</span>

    <span class="c1">// ommitted</span>
<span class="p">};</span>
</pre></div>
</div>
<p>Consider the above examples again. In order for InferBound to determine how many elements of C must be computed, it is important to know whether the computation of C occurs within the scope of a leaf variable of D, or above that scope. For example, in Ex. 1, the computation of C occurs  <em>above</em>  the scopes of all of D’s leaf variables. In Ex. 2, the computation of C occurs  <em>within</em>  the scope of all of D’s leaf variables. In Ex. 3, C occurs within the scope of D’s i, but above the scope of D’s j.</p>
<p>CreateAttachPath is responsible for figuring out which scopes contain a stage C. These scopes are ordered from innermost scope to outermost. Thus for each stage CreateAttachPath produces an “attach path”, which lists the scopes containing the stage, from innermost to outermost scope. In Ex. 1, the attach path of C is empty. In Ex. 2, the attach path of C contains {j, i}. In Ex. 3, the attach path of C is {i}.</p>
<p>The following example clarifies the concept of an attach path, for a more complicated case.</p>
<p><strong>Ex. 4</strong></p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">C</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span> <span class="p">:</span> <span class="n">tvm</span><span class="o">.</span><span class="n">const</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="s2">&quot;int32&quot;</span><span class="p">),</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;C&#39;</span><span class="p">)</span>
<span class="n">D</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">di</span><span class="p">,</span> <span class="n">dj</span><span class="p">,</span> <span class="n">dk</span> <span class="p">:</span> <span class="n">C</span><span class="p">[</span><span class="n">dj</span><span class="p">,</span> <span class="n">dk</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;D&#39;</span><span class="p">)</span>
<span class="n">s</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">create_schedule</span><span class="p">(</span><span class="n">D</span><span class="o">.</span><span class="n">op</span><span class="p">)</span>
<span class="n">s</span><span class="p">[</span><span class="n">C</span><span class="p">]</span><span class="o">.</span><span class="n">compute_at</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">D</span><span class="p">],</span> <span class="n">D</span><span class="o">.</span><span class="n">op</span><span class="o">.</span><span class="n">axis</span><span class="p">[</span><span class="mi">2</span><span class="p">])</span>
</pre></div>
</div>
<p>Here is the IR after ScheduleOps (note that loops with extent 1 have been preserved, using the <code class="docutils literal notranslate"><span class="pre">debug_keep_trivial_loop</span></code> argument of ScheduleOps):</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">realize</span> <span class="n">D</span><span class="p">([</span><span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">5</span><span class="p">],</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">16</span><span class="p">])</span> <span class="p">{</span>
  <span class="n">produce</span> <span class="n">D</span> <span class="p">{</span>
    <span class="k">for</span> <span class="p">(</span><span class="n">di</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="p">{</span>
      <span class="k">for</span> <span class="p">(</span><span class="n">dj</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">dk</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span><span class="p">)</span> <span class="p">{</span>
          <span class="n">realize</span> <span class="n">C</span><span class="p">([</span><span class="n">dj</span><span class="p">,</span> <span class="mi">1</span><span class="p">],</span> <span class="p">[</span><span class="n">dk</span><span class="p">,</span> <span class="mi">1</span><span class="p">])</span> <span class="p">{</span>
            <span class="n">produce</span> <span class="n">C</span> <span class="p">{</span>
              <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
                <span class="k">for</span> <span class="p">(</span><span class="n">j</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
                  <span class="n">C</span><span class="p">((</span><span class="n">i</span> <span class="o">+</span> <span class="n">dj</span><span class="p">),</span> <span class="p">(</span><span class="n">j</span> <span class="o">+</span> <span class="n">dk</span><span class="p">))</span> <span class="o">=</span><span class="mi">5</span>
                <span class="p">}</span>
              <span class="p">}</span>
            <span class="p">}</span>
            <span class="n">D</span><span class="p">(</span><span class="n">di</span><span class="p">,</span> <span class="n">dj</span><span class="p">,</span> <span class="n">dk</span><span class="p">)</span> <span class="o">=</span><span class="p">(</span><span class="n">C</span><span class="p">(</span><span class="n">dj</span><span class="p">,</span> <span class="n">dk</span><span class="p">)</span><span class="o">*</span><span class="mi">2</span><span class="p">)</span>
          <span class="p">}</span>
        <span class="p">}</span>
      <span class="p">}</span>
    <span class="p">}</span>
  <span class="p">}</span>
<span class="p">}</span>
</pre></div>
</div>
<p>In this case, the attach path of C is {dk, dj, di}. Note that C does not use di, but di still appears in C’s attach path.</p>
<p><strong>Ex. 5</strong></p>
<p>Compute_at is commonly applied after splitting, but this can be handled very naturally given the above definitions. In the example below, the attachment point of C is j_inner of D. The attach path of C is {j_inner, j_outer, i}.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">C</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span> <span class="p">:</span> <span class="n">tvm</span><span class="o">.</span><span class="n">const</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="s2">&quot;int32&quot;</span><span class="p">),</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;C&#39;</span><span class="p">)</span>
<span class="n">D</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span> <span class="p">:</span> <span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;D&#39;</span><span class="p">)</span>
<span class="n">s</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">create_schedule</span><span class="p">(</span><span class="n">D</span><span class="o">.</span><span class="n">op</span><span class="p">)</span>
<span class="n">d_o</span><span class="p">,</span> <span class="n">d_i</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">D</span><span class="p">]</span><span class="o">.</span><span class="n">split</span><span class="p">(</span><span class="n">D</span><span class="o">.</span><span class="n">op</span><span class="o">.</span><span class="n">axis</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span> <span class="n">factor</span><span class="o">=</span><span class="mi">8</span><span class="p">)</span>
<span class="n">s</span><span class="p">[</span><span class="n">C</span><span class="p">]</span><span class="o">.</span><span class="n">compute_at</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">D</span><span class="p">],</span> <span class="n">d_i</span><span class="p">)</span>
</pre></div>
</div>
<p>The IR in this case looks like:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">i</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span>
    <span class="k">for</span> <span class="n">j_outer</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">2</span>
        <span class="k">for</span> <span class="n">j_inner</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">8</span>
            <span class="n">C</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">5</span>
            <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="n">j_outer</span><span class="o">*</span><span class="mi">8</span> <span class="o">+</span> <span class="n">j_inner</span><span class="p">]</span> <span class="o">=</span> <span class="n">C</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span>
</pre></div>
</div>
</div>
<div class="section" id="building-an-attach-path">
<h3>Building an Attach Path<a class="headerlink" href="#building-an-attach-path" title="永久链接至标题">¶</a></h3>
<p>We continue to refer to stages C and D, as introduced in the previous section. The CreateAttachPath algorithm builds the attach path of a stage C as follows. If C does not have attach_type <code class="docutils literal notranslate"><span class="pre">kScope</span></code>, then C has no attachment, and C’s attach path is empty. Otherwise, C is attached at attach_stage=D. We iterate through D’s leaf variables in top-down order. All leaf variables starting from C.attach_ivar and lower are added to C’s attach path. Then, if D is also attached somewhere, e.g., to stage E, the process is repeated for E’s leaves. Thus CreateAttachPath continues to add variables to C’s attach path until a stage with no attachment is encountered.</p>
<p>In the example below, C is attached at D, and D is attached at E.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">C</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">ci</span><span class="p">,</span> <span class="n">cj</span> <span class="p">:</span> <span class="n">tvm</span><span class="o">.</span><span class="n">const</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="s2">&quot;int32&quot;</span><span class="p">),</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;C&#39;</span><span class="p">)</span>
<span class="n">D</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">di</span><span class="p">,</span> <span class="n">dj</span> <span class="p">:</span> <span class="n">C</span><span class="p">[</span><span class="n">di</span><span class="p">,</span> <span class="n">dj</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;D&#39;</span><span class="p">)</span>
<span class="n">E</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">ei</span><span class="p">,</span> <span class="n">ej</span> <span class="p">:</span> <span class="n">D</span><span class="p">[</span><span class="n">ei</span><span class="p">,</span> <span class="n">ej</span><span class="p">]</span><span class="o">*</span><span class="mi">4</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;E&#39;</span><span class="p">)</span>
<span class="n">s</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">create_schedule</span><span class="p">(</span><span class="n">E</span><span class="o">.</span><span class="n">op</span><span class="p">)</span>
<span class="n">s</span><span class="p">[</span><span class="n">C</span><span class="p">]</span><span class="o">.</span><span class="n">compute_at</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">D</span><span class="p">],</span> <span class="n">D</span><span class="o">.</span><span class="n">op</span><span class="o">.</span><span class="n">axis</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
<span class="n">s</span><span class="p">[</span><span class="n">D</span><span class="p">]</span><span class="o">.</span><span class="n">compute_at</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">E</span><span class="p">],</span> <span class="n">E</span><span class="o">.</span><span class="n">op</span><span class="o">.</span><span class="n">axis</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
</pre></div>
</div>
<p>With <code class="docutils literal notranslate"><span class="pre">debug_keep_trivial_loop=True</span></code>, the attach path of C is {dj, di, ej, ei}, and the attach path of D is {ej, ei}:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">//</span> <span class="n">attr</span> <span class="p">[</span><span class="n">D</span><span class="p">]</span> <span class="n">storage_scope</span> <span class="o">=</span> <span class="s2">&quot;global&quot;</span>
<span class="n">allocate</span> <span class="n">D</span><span class="p">[</span><span class="n">int32</span> <span class="o">*</span> <span class="mi">1</span><span class="p">]</span>
<span class="o">//</span> <span class="n">attr</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">storage_scope</span> <span class="o">=</span> <span class="s2">&quot;global&quot;</span>
<span class="n">allocate</span> <span class="n">C</span><span class="p">[</span><span class="n">int32</span> <span class="o">*</span> <span class="mi">1</span><span class="p">]</span>
<span class="n">produce</span> <span class="n">E</span> <span class="p">{</span>
  <span class="k">for</span> <span class="p">(</span><span class="n">ei</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">for</span> <span class="p">(</span><span class="n">ej</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span><span class="p">)</span> <span class="p">{</span>
      <span class="n">produce</span> <span class="n">D</span> <span class="p">{</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">di</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
          <span class="k">for</span> <span class="p">(</span><span class="n">dj</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">produce</span> <span class="n">C</span> <span class="p">{</span>
              <span class="k">for</span> <span class="p">(</span><span class="n">ci</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
                <span class="k">for</span> <span class="p">(</span><span class="n">cj</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
                  <span class="n">C</span><span class="p">[(</span><span class="n">ci</span> <span class="o">+</span> <span class="n">cj</span><span class="p">)]</span> <span class="o">=</span> <span class="mi">5</span>
                <span class="p">}</span>
              <span class="p">}</span>
            <span class="p">}</span>
            <span class="n">D</span><span class="p">[(</span><span class="n">di</span> <span class="o">+</span> <span class="n">dj</span><span class="p">)]</span> <span class="o">=</span> <span class="p">(</span><span class="n">C</span><span class="p">[(</span><span class="n">di</span> <span class="o">+</span> <span class="n">dj</span><span class="p">)]</span><span class="o">*</span><span class="mi">2</span><span class="p">)</span>
          <span class="p">}</span>
        <span class="p">}</span>
      <span class="p">}</span>
      <span class="n">E</span><span class="p">[((</span><span class="n">ei</span><span class="o">*</span><span class="mi">16</span><span class="p">)</span> <span class="o">+</span> <span class="n">ej</span><span class="p">)]</span> <span class="o">=</span> <span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="mi">4</span><span class="p">)</span>
    <span class="p">}</span>
  <span class="p">}</span>
<span class="p">}</span>
</pre></div>
</div>
</div>
<div class="section" id="id2">
<h3>InferBound with compute_at<a class="headerlink" href="#id2" title="永久链接至标题">¶</a></h3>
<p>Now that the concept of an attach path has been introduced, we return to how InferBound differs if the schedule contains compute_at. The only difference is in InferRootBound, <a class="reference internal" href="#phase1"><span class="std std-ref">Phase 1: Initialize IntSets for consumer’s leaf_iter_vars</span></a> and <a class="reference internal" href="#phase2"><span class="std std-ref">Phase 2: Propagate IntSets from consumer’s leaves to consumer’s roots</span></a>.</p>
<p>In InferRootBound, the goal is to determine Ranges for the root_iter_vars of a particular stage, C. Phases 1-2 of InferRootBound assign IntSets to the leaf IterVars of C’s consumers, and then propagate those IntSets up to the consumers’ root_iter_vars.</p>
<p>If there are no attachments, the Ranges already computed for the consumer’s variables define how much of C is needed by the consumer. However, if the stage is actually inside the scope of one of the consumer’s variables j, then only a single point within the Range of j is needed at a time.</p>
</div>
<div class="section" id="phase1ca">
<span id="id3"></span><h3>Phase 1: Initialize IntSets for consumer’s leaf_iter_vars<a class="headerlink" href="#phase1ca" title="永久链接至标题">¶</a></h3>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="cm">/*</span>
<span class="cm"> * Input: Map&lt;IterVar, Range&gt; rmap: contains the Range for each IterVar of the consumer stage</span>
<span class="cm"> * Output: Map&lt;IterVar, IntSet&gt; up_state: contains an IntSet for each leaf_iter_var of the consumer</span>
<span class="cm"> */</span>
</pre></div>
</div>
<p>In Phase 1, IntSets for each of the consumer’s leaf_iter_vars are created, based on the Ranges of the leaf_iter_vars from rmap. Recall that the consumer has already been visited by InferBound, so all of its IterVars have known Ranges in rmap.</p>
<p>有以下三种情况：</p>
<ul class="simple">
<li><p>Case 1: Extent of leaf var’s Range is 1. In this case, the up_state for the leaf is just a single point, equal to the Range’s min.</p></li>
<li><p>Case 2: No relaxation is needed. In this case, the up_state for the leaf is just a single point, defined by the leaf var itself.</p></li>
<li><p>Case 3: Relaxation is needed. In this case, the leaf’s Range is simply converted to an IntSet.</p></li>
</ul>
<p>Case 2 occurs if we encounter the attachment point of stage C in the consumer. For this attach_ivar, and all higher leaf variables of the consumer, Case 2 will be applied. This ensures that only a single point within the Range of the leaf variable will be requested, if C is inside the leaf variable’s scope.</p>
</div>
<div class="section" id="phase2ca">
<span id="id4"></span><h3>Phase 2: Propagate IntSets from consumer’s leaves to consumer’s roots<a class="headerlink" href="#phase2ca" title="永久链接至标题">¶</a></h3>
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="cm">/*</span>
<span class="cm"> * Input: Map&lt;IterVar, IntSet&gt; up_state: consumer leaf -&gt; IntSet</span>
<span class="cm"> * Output: Map&lt;IterVar, IntSet&gt; dom_map: consumer root -&gt; IntSet</span>
<span class="cm"> */</span>
</pre></div>
</div>
<p>Phase 2 begins by calling PassUpDomain, which visits the IterVarRelations of the consumer stage. In the case of a Split relation, PassUpDomain sets the up_state of the parent IterVar, based on the inner and outer IntSets, as follows:</p>
<ul class="simple">
<li><p>Case 1: The Ranges of outer and inner IterVars match their <code class="docutils literal notranslate"><span class="pre">up_state</span></code> domains. In this case, set the parent’s <code class="docutils literal notranslate"><span class="pre">up_state</span></code> by simply converting the parent’s Range to an IntSet.</p></li>
<li><p>Case 2: Otherwise, the parent’s <code class="docutils literal notranslate"><span class="pre">up_state</span></code> is defined by evaluating <code class="docutils literal notranslate"><span class="pre">outer*f</span> <span class="pre">+</span> <span class="pre">inner</span> <span class="pre">+</span> <span class="pre">rmap[parent]-&gt;min</span></code>, with respect to the <code class="docutils literal notranslate"><span class="pre">up_state</span></code> of outer and inner. Here, instead of using the Split relation’s factor, TVM uses* <code class="docutils literal notranslate"><span class="pre">f</span> <span class="pre">=</span> <span class="pre">rmap[inner]-&gt;extent</span></code>.</p></li>
</ul>
<p>Now, because the schedule contains compute_at, it is possible for Case 2 to apply. This is because the leaf IntSets may now be initialized to a single point within their Range (Case 2 of <a class="reference internal" href="#phase1ca"><span class="std std-ref">Phase 1: Initialize IntSets for consumer’s leaf_iter_vars</span></a>), so the IntSets will no longer always match the Ranges.</p>
<p>After PassUpDomain has finished propagating up_state to all IterVars of the consumer, a fresh map, from root_iter_vars to IntSet, is created. If the stage is not attached to the current consumer, then for each variable iv in the consumer’s attach_path, iv’s Range is added to a <code class="docutils literal notranslate"><span class="pre">relax_set</span></code>. The root variables of the stage are evaluated with respect to this <code class="docutils literal notranslate"><span class="pre">relax_set</span></code>.</p>
<p>This is to handle cases like the following example, where C is not attached anywhere, but its consumer D is attached in stage E. In this case, D’s attach_path, {ej, ei} must be considered when determining how much of C must be computed.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">C</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">ci</span><span class="p">,</span> <span class="n">cj</span> <span class="p">:</span> <span class="n">tvm</span><span class="o">.</span><span class="n">const</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="s2">&quot;int32&quot;</span><span class="p">),</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;C&#39;</span><span class="p">)</span>
<span class="n">D</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">di</span><span class="p">,</span> <span class="n">dj</span> <span class="p">:</span> <span class="n">C</span><span class="p">[</span><span class="n">di</span><span class="p">,</span> <span class="n">dj</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;D&#39;</span><span class="p">)</span>
<span class="n">E</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="mi">5</span><span class="p">,</span> <span class="mi">16</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">ei</span><span class="p">,</span> <span class="n">ej</span> <span class="p">:</span> <span class="n">D</span><span class="p">[</span><span class="n">ei</span><span class="p">,</span> <span class="n">ej</span><span class="p">]</span><span class="o">*</span><span class="mi">4</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;E&#39;</span><span class="p">)</span>
<span class="n">s</span> <span class="o">=</span> <span class="n">tvm</span><span class="o">.</span><span class="n">create_schedule</span><span class="p">(</span><span class="n">E</span><span class="o">.</span><span class="n">op</span><span class="p">)</span>
<span class="n">s</span><span class="p">[</span><span class="n">D</span><span class="p">]</span><span class="o">.</span><span class="n">compute_at</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">E</span><span class="p">],</span> <span class="n">E</span><span class="o">.</span><span class="n">op</span><span class="o">.</span><span class="n">axis</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">ci</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span>
    <span class="k">for</span> <span class="n">cj</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span>
        <span class="n">C</span><span class="p">[</span><span class="n">ci</span><span class="p">,</span> <span class="n">cj</span><span class="p">]</span> <span class="o">=</span> <span class="mi">5</span>
<span class="k">for</span> <span class="n">ei</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">5</span>
    <span class="k">for</span> <span class="n">ej</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">16</span>
        <span class="n">D</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">C</span><span class="p">[</span><span class="n">ei</span><span class="p">,</span> <span class="n">ej</span><span class="p">]</span><span class="o">*</span><span class="mi">2</span>
        <span class="n">E</span><span class="p">[</span><span class="n">ei</span><span class="p">,</span> <span class="n">ej</span><span class="p">]</span> <span class="o">=</span> <span class="n">D</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="mi">4</span>
</pre></div>
</div>
</div>
<div class="section" id="limitations-of-passupdomain">
<h3>Limitations of PassUpDomain<a class="headerlink" href="#limitations-of-passupdomain" title="永久链接至标题">¶</a></h3>
<p>This section describes known limitations of PassUpDomain. These limitations affect the Ranges produced by InferBound, as well as other users of PassUpDomain such as <code class="docutils literal notranslate"><span class="pre">tensorize</span></code>.</p>
<p><strong>Ex. 6</strong></p>
<p>Above, we discussed the behavior of PassUpDomain on Split relations only. In the following example, the schedule contains <code class="docutils literal notranslate"><span class="pre">fuse</span></code> in addition to <code class="docutils literal notranslate"><span class="pre">split</span></code>. In the TVM program below, the operation C has two axes that are fused, and then the fused axis is split. Note that all tensors are originally of shape <code class="docutils literal notranslate"><span class="pre">(4,</span> <span class="pre">4)</span></code> and the fused axis is split by factor <code class="docutils literal notranslate"><span class="pre">4</span></code> as well. Therefore, it would be natural to assume that the effect of the fuse is simply undone by the split. However, this is not the case in TVM, as explained below.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">tvm</span>
<span class="kn">from</span> <span class="nn">tvm</span> <span class="k">import</span> <span class="n">te</span>

<span class="n">n</span> <span class="o">=</span> <span class="mi">4</span>
<span class="n">m</span> <span class="o">=</span> <span class="mi">4</span>

<span class="n">A</span> <span class="o">=</span> <span class="n">te</span><span class="o">.</span><span class="n">placeholder</span><span class="p">((</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">),</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;A&#39;</span><span class="p">)</span>
<span class="n">B</span> <span class="o">=</span> <span class="n">te</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">bi</span><span class="p">,</span> <span class="n">bj</span><span class="p">:</span> <span class="n">A</span><span class="p">[</span><span class="n">bi</span><span class="p">,</span> <span class="n">bj</span><span class="p">]</span><span class="o">+</span><span class="mi">2</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;B&#39;</span><span class="p">)</span>
<span class="n">C</span> <span class="o">=</span> <span class="n">te</span><span class="o">.</span><span class="n">compute</span><span class="p">((</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">),</span> <span class="k">lambda</span> <span class="n">ci</span><span class="p">,</span> <span class="n">cj</span><span class="p">:</span> <span class="n">B</span><span class="p">[</span><span class="n">ci</span><span class="p">,</span> <span class="n">cj</span><span class="p">]</span><span class="o">*</span><span class="mi">3</span><span class="p">,</span> <span class="n">name</span><span class="o">=</span><span class="s1">&#39;C&#39;</span><span class="p">)</span>

<span class="n">s</span> <span class="o">=</span> <span class="n">te</span><span class="o">.</span><span class="n">create_schedule</span><span class="p">(</span><span class="n">C</span><span class="o">.</span><span class="n">op</span><span class="p">)</span>

<span class="n">fused_axes</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">C</span><span class="p">]</span><span class="o">.</span><span class="n">fuse</span><span class="p">(</span><span class="n">C</span><span class="o">.</span><span class="n">op</span><span class="o">.</span><span class="n">axis</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">C</span><span class="o">.</span><span class="n">op</span><span class="o">.</span><span class="n">axis</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
<span class="n">xo</span><span class="p">,</span> <span class="n">xi</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">C</span><span class="p">]</span><span class="o">.</span><span class="n">split</span><span class="p">(</span><span class="n">fused_axes</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span>

<span class="n">s</span><span class="p">[</span><span class="n">B</span><span class="p">]</span><span class="o">.</span><span class="n">compute_at</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">C</span><span class="p">],</span> <span class="n">xo</span><span class="p">)</span>

<span class="nb">print</span><span class="p">(</span><span class="n">tvm</span><span class="o">.</span><span class="n">lower</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="p">[</span><span class="n">A</span><span class="p">,</span> <span class="n">C</span><span class="p">],</span> <span class="n">simple_mode</span><span class="o">=</span><span class="kc">True</span><span class="p">))</span>
</pre></div>
</div>
<p>The output of this program is shown below. Notice that all 16 elements of B are computed every time through the outer loop, even though C only uses 4 of them.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">//</span> <span class="n">attr</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="n">storage_scope</span> <span class="o">=</span> <span class="s2">&quot;global&quot;</span>
<span class="n">allocate</span> <span class="n">B</span><span class="p">[</span><span class="n">float32</span> <span class="o">*</span> <span class="mi">16</span><span class="p">]</span>
<span class="n">produce</span> <span class="n">C</span> <span class="p">{</span>
  <span class="k">for</span> <span class="p">(</span><span class="n">ci</span><span class="o">.</span><span class="n">cj</span><span class="o">.</span><span class="n">fused</span><span class="o">.</span><span class="n">outer</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">produce</span> <span class="n">B</span> <span class="p">{</span>
      <span class="k">for</span> <span class="p">(</span><span class="n">bi</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">bj</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="p">{</span>
          <span class="n">B</span><span class="p">[((</span><span class="n">bi</span><span class="o">*</span><span class="mi">4</span><span class="p">)</span> <span class="o">+</span> <span class="n">bj</span><span class="p">)]</span> <span class="o">=</span> <span class="p">(</span><span class="n">A</span><span class="p">[((</span><span class="n">bi</span><span class="o">*</span><span class="mi">4</span><span class="p">)</span> <span class="o">+</span> <span class="n">bj</span><span class="p">)]</span> <span class="o">+</span> <span class="mf">2.000000</span><span class="n">f</span><span class="p">)</span>
        <span class="p">}</span>
      <span class="p">}</span>
    <span class="p">}</span>
    <span class="k">for</span> <span class="p">(</span><span class="n">ci</span><span class="o">.</span><span class="n">cj</span><span class="o">.</span><span class="n">fused</span><span class="o">.</span><span class="n">inner</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="p">{</span>
      <span class="n">C</span><span class="p">[((</span><span class="n">ci</span><span class="o">.</span><span class="n">cj</span><span class="o">.</span><span class="n">fused</span><span class="o">.</span><span class="n">outer</span><span class="o">*</span><span class="mi">4</span><span class="p">)</span> <span class="o">+</span> <span class="n">ci</span><span class="o">.</span><span class="n">cj</span><span class="o">.</span><span class="n">fused</span><span class="o">.</span><span class="n">inner</span><span class="p">)]</span> <span class="o">=</span> <span class="p">(</span><span class="n">B</span><span class="p">[((</span><span class="n">ci</span><span class="o">.</span><span class="n">cj</span><span class="o">.</span><span class="n">fused</span><span class="o">.</span><span class="n">outer</span><span class="o">*</span><span class="mi">4</span><span class="p">)</span> <span class="o">+</span> <span class="n">ci</span><span class="o">.</span><span class="n">cj</span><span class="o">.</span><span class="n">fused</span><span class="o">.</span><span class="n">inner</span><span class="p">)]</span><span class="o">*</span><span class="mf">3.000000</span><span class="n">f</span><span class="p">)</span>
    <span class="p">}</span>
  <span class="p">}</span>
<span class="p">}</span>
</pre></div>
</div>
<p>This is in contrast to the following IR, which is produced by modifying the above program by deleting the fuse and split, and replacing the compute_at with <code class="docutils literal notranslate"><span class="pre">s[B].compute_at(s[C],</span> <span class="pre">C.op.axis[0])</span></code>. Note that in the IR below, only 4 elements of B are computed at a time, as desired. The size of buffer B is also smaller.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">//</span> <span class="n">attr</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="n">storage_scope</span> <span class="o">=</span> <span class="s2">&quot;global&quot;</span>
<span class="n">allocate</span> <span class="n">B</span><span class="p">[</span><span class="n">float32</span> <span class="o">*</span> <span class="mi">4</span><span class="p">]</span>
<span class="n">produce</span> <span class="n">C</span> <span class="p">{</span>
  <span class="k">for</span> <span class="p">(</span><span class="n">ci</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">produce</span> <span class="n">B</span> <span class="p">{</span>
      <span class="k">for</span> <span class="p">(</span><span class="n">bj</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">B</span><span class="p">[</span><span class="n">bj</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">A</span><span class="p">[((</span><span class="n">ci</span><span class="o">*</span><span class="mi">4</span><span class="p">)</span> <span class="o">+</span> <span class="n">bj</span><span class="p">)]</span> <span class="o">+</span> <span class="mf">2.000000</span><span class="n">f</span><span class="p">)</span>
      <span class="p">}</span>
    <span class="p">}</span>
    <span class="k">for</span> <span class="p">(</span><span class="n">cj</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="p">{</span>
      <span class="n">C</span><span class="p">[((</span><span class="n">ci</span><span class="o">*</span><span class="mi">4</span><span class="p">)</span> <span class="o">+</span> <span class="n">cj</span><span class="p">)]</span> <span class="o">=</span> <span class="p">(</span><span class="n">B</span><span class="p">[</span><span class="n">cj</span><span class="p">]</span><span class="o">*</span><span class="mf">3.000000</span><span class="n">f</span><span class="p">)</span>
    <span class="p">}</span>
  <span class="p">}</span>
<span class="p">}</span>
</pre></div>
</div>
<p>This example demonstrates that contrary to what we expect, the split does not simply undo the fuse. So what causes the difference? Why is the entire tensor B re-computed 4 times, when only a single row is actually needed at a time?</p>
<p>Determining the amount of B that must be computed is the responsibility of InferBound. However, the Ranges returned by InferBound for B’s root_iter_vars are too large in this case: <code class="docutils literal notranslate"><span class="pre">[0,</span> <span class="pre">4]</span></code> for both <code class="docutils literal notranslate"><span class="pre">bi</span></code> and <code class="docutils literal notranslate"><span class="pre">bj</span></code>.  This occurs because of a limitation in PassUpDomain on Fuse relations, which we explain next.</p>
<p>When InferRootBound is working on stage B, it visits B’s consumer stage C to find out how much of B is requested by C. C has root_iter_vars ci and cj, which have been fused and then split. This results in the following <a class="reference internal" href="#itervarhypergraph"><span class="std std-ref">IterVar 超图</span></a> for stage C.</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/passupdomain_problem.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/passupdomain_problem.png" />
<p>We trace the execution of InferRootBound on stage B. Recall that <a class="reference internal" href="#phase1ca"><span class="std std-ref">Phase 1: Initialize IntSets for consumer’s leaf_iter_vars</span></a> of InferRootBound involves setting the IntSets for all leaf_iter_vars of B’s consumer stage C. In this case, C’s leaf_iter_vars are <code class="docutils literal notranslate"><span class="pre">ci.cj.fused.outer</span></code> and <code class="docutils literal notranslate"><span class="pre">ci.cj.fused.inner</span></code>.  Since B is attached at <code class="docutils literal notranslate"><span class="pre">ci.cj.fused.outer</span></code>, <code class="docutils literal notranslate"><span class="pre">ci.cj.fused.inner</span></code> must be relaxed but <code class="docutils literal notranslate"><span class="pre">ci.cj.fused.outer</span></code> is a single point. The IntSets of C’s leaf_iter_vars, after <a class="reference internal" href="#phase1ca"><span class="std std-ref">Phase 1: Initialize IntSets for consumer’s leaf_iter_vars</span></a>, are shown in the following table.</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 30%" />
<col style="width: 70%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>IterVar</p></th>
<th class="head"><p>IntSet after Phase 1</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">ci.cj.fused.inner</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[0,</span> <span class="pre">(min(4,</span> <span class="pre">(16</span> <span class="pre">-</span> <span class="pre">(ci.cj.fused.outer*4)))</span> <span class="pre">-</span> <span class="pre">1)]</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">ci.cj.fused.outer</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[ci.cj.fused.outer,</span> <span class="pre">ci.cj.fused.outer]</span></code></p></td>
</tr>
</tbody>
</table>
<p>In <a class="reference internal" href="#phase2ca"><span class="std std-ref">Phase 2: Propagate IntSets from consumer’s leaves to consumer’s roots</span></a> of InferRootBound, PassUpDomain is called on all of C’s IterVarRelations in bottom-up order.</p>
<p>PassUpDomain is called on C’s Split node first. Case 2 of PassUpDomain applies, because the IntSet of <code class="docutils literal notranslate"><span class="pre">ci.cj.fused.outer</span></code> is just a single point, and doesn’t equal its Range (as previously computed by InferBound on stage C). PassUpDomain therefore sets the IntSet of <code class="docutils literal notranslate"><span class="pre">ci.cj.fused</span></code> based on the IntSets of <code class="docutils literal notranslate"><span class="pre">ci.cj.fused.inner</span></code> and <code class="docutils literal notranslate"><span class="pre">ci.cj.fused.outer</span></code>, as shown in row 3 of the following table.</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 18%" />
<col style="width: 82%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>IterVar</p></th>
<th class="head"><p>IntSet after PassUpDomain on SplitNode</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">ci.cj.fused.inner</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[0,</span> <span class="pre">(min(4,</span> <span class="pre">(16</span> <span class="pre">-</span> <span class="pre">(ci.cj.fused.outer*4)))</span> <span class="pre">-</span> <span class="pre">1)]</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">ci.cj.fused.outer</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[ci.cj.fused.outer,</span> <span class="pre">ci.cj.fused.outer]</span></code></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">ci.cj.fused</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[(ci.cj.fused.outer*4),</span> <span class="pre">((ci.cj.fused.outer*4)</span> <span class="pre">+</span> <span class="pre">(min(4,</span> <span class="pre">(16</span> <span class="pre">-</span> <span class="pre">(ci.cj.fused.outer*4)))</span> <span class="pre">-</span> <span class="pre">1))]</span></code></p></td>
</tr>
</tbody>
</table>
<p>After PassUpDomain is called on the Split node, it is called on the Fuse node.</p>
<ul class="simple">
<li><p>Case 1: the Range of IterVar <code class="docutils literal notranslate"><span class="pre">fused</span></code> (i.e., as previously calculated by InferBound) is equal to its IntSet</p></li>
<li><p>Case 2: the IntSet of IterVar <code class="docutils literal notranslate"><span class="pre">fused</span></code> is a single point</p></li>
<li><p>Case 3: otherwise</p></li>
</ul>
<p>In our case, the Range of <code class="docutils literal notranslate"><span class="pre">ci.cj.fused</span></code>, is [0, 16). This is not equal to the IntSet of <code class="docutils literal notranslate"><span class="pre">ci.cj.fused</span></code>, which has extent at most 4 (see row 3 of the table above). Therefore Case 1 does not apply.  Case 2 doesn’t apply either, since the IntSet of <code class="docutils literal notranslate"><span class="pre">ci.cj.fused</span></code> is not a single point.  Therefore, only the default Case 3 applies.</p>
<p>Unfortunately in Case 3, PassUpDomain conservatively applies a “fallback inference rule”, i.e., it just returns IntSets equal to the Ranges of <code class="docutils literal notranslate"><span class="pre">ci</span></code> and <code class="docutils literal notranslate"><span class="pre">cj</span></code>. Since C is the output stage of the schedule, we know that InferBound will have set the Ranges of the root_iter_vars of C (i.e., <code class="docutils literal notranslate"><span class="pre">ci</span></code> and <code class="docutils literal notranslate"><span class="pre">cj</span></code>) to their original dimensions (i.e., the <code class="docutils literal notranslate"><span class="pre">dom</span></code> value of their IterVars). The resulting output of PassUpDomain for <code class="docutils literal notranslate"><span class="pre">ci</span></code> and <code class="docutils literal notranslate"><span class="pre">cj</span></code> is shown in the last two rows of the table below.</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 18%" />
<col style="width: 82%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>IterVar</p></th>
<th class="head"><p>IntSet after PassUpDomain on FuseNode</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">ci.cj.fused.inner</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[0,</span> <span class="pre">(min(4,</span> <span class="pre">(16</span> <span class="pre">-</span> <span class="pre">(ci.cj.fused.outer*4)))</span> <span class="pre">-</span> <span class="pre">1)]</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">ci.cj.fused.outer</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[ci.cj.fused.outer,</span> <span class="pre">ci.cj.fused.outer]</span></code></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">ci.cj.fused</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[(ci.cj.fused.outer*4),</span> <span class="pre">((ci.cj.fused.outer*4)</span> <span class="pre">+</span> <span class="pre">(min(4,</span> <span class="pre">(16</span> <span class="pre">-</span> <span class="pre">(ci.cj.fused.outer*4)))</span> <span class="pre">-</span> <span class="pre">1))]</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">ci</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[0,</span> <span class="pre">4]</span></code></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">cj</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[0,</span> <span class="pre">4]</span></code></p></td>
</tr>
</tbody>
</table>
<p>This is enough to guarantee that consumer C requests <em>all</em> elements of B: the IntSets of <code class="docutils literal notranslate"><span class="pre">ci</span></code> and <code class="docutils literal notranslate"><span class="pre">cj</span></code> become requests from consumer C to the output tensors of stage B (via PropBoundToInputs in <a class="reference internal" href="#phase3"><span class="std std-ref">Phase 3: Propagate IntSets to consumer’s input tensors</span></a> and GatherBound in <a class="reference internal" href="#phase4"><span class="std std-ref">Phase 4: Consolidate across all consumers</span></a>).</p>
<p>This example shows that schedules containing a split of fused axes are difficult to handle in TVM. The source of the difficulty is similar to the limitations of GatherBound. The region of tensor B requested by a consumer C must be a single rectangular region of B. Or, if B has more than two dimensions, the region of B must be expressible as an independent Range for each of its axes.</p>
<p>If the split factor is 4, or 8, in the above example, the region of B needed in each iteration of the outer loop is rectangular.</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/passupdomain_div.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/passupdomain_div.png" />
<p>However, if the split factor is changed from 4 to 3 in the example above, it is easy to see that the region of B that C needs can no longer be described by an independent Range for each of its axes.</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/passupdomain_nodiv.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/passupdomain_nodiv.png" />
<p>The best that can be done with rectangular regions is shown in the following diagram. The orange regions are the minimum rectangular regions covering the region of B that needs to be computed, at each iteration of the outer loop.</p>
<img alt="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/passupdomain_min.png" class="align-center" src="https://raw.githubusercontent.com/tvmai/tvmai.github.io/main/images/docs/inferbound/passupdomain_min.png" />
</div>
</div>
</div>


           </div>
           
          </div>
          

<footer>

    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="hybrid_script.html" class="btn btn-neutral float-right" title="混合前端开发指南" accesskey="n" rel="next">下一个 <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="pass_infra.html" class="btn btn-neutral float-left" title="Pass Infrastructure" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> 上一个</a>
      
    </div>

<div id="button" class="backtop"><img src="../_static//img/right.svg" alt="backtop"/> </div>
<section class="footerSec">
    <div class="footerHeader">
      <ul class="d-flex align-md-items-center justify-content-between flex-column flex-md-row">
        <li class="copywrite d-flex align-items-center">
          <h5 id="copy-right-info">© 2020 Apache Software Foundation | All right reserved</h5>
        </li>
      </ul>

    </div>

    <ul>
      <li class="footernote">Copyright © 2020 The Apache Software Foundation. Apache TVM, Apache, the Apache feather, and the Apache TVM project logo are either trademarks or registered trademarks of the Apache Software Foundation.</li>
    </ul>

</section>
</footer>
        </div>
      </div>

    </section>

  </div>
  

    <script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.12.9/umd/popper.min.js" integrity="sha384-ApNbgh9B+Y1QKtv3Rn7W3mgPxhU9K/ScQsAP7hUibX39j7fakFPskvXusvfa0b4Q" crossorigin="anonymous"></script>
    <script src="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/js/bootstrap.min.js" integrity="sha384-JZR6Spejh4U02d8jOt6vLEHfe/JQGiRRSQQxSfFWpi1MquVdAyjUar5+76PVCmYl" crossorigin="anonymous"></script>

  </body>
  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
    <!-- Theme Analytics -->
    <script>
    (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
      (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
      m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
    })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

    ga('create', 'UA-75982049-2', 'auto');
    ga('send', 'pageview');
    </script>

    
   

</body>
</html>